package tcts0421;
// https://leetcode-cn.com/problems/sparse-array-search-lcci/
public class 面试题1005稀疏数组搜索0421 {

         public int findString1(String[] words, String s) {
             for(int i=0;i<words.length;i++){
                 if(words[i].equals(s)){
                     return i;
                 }
             }
             return -1;
         }
        public int findString2(String[] words, String s) {
            int l = 0, r = words.length-1;
            while(r >= l){
                int m = (l + r) >> 1;
                //当前位置为""，mid前移，就这一个和普通二分不同，其他一模一样
                while(m > l &&  words[m].equals("")) m--;
                if(s.compareTo(words[m]) == 0) return m;
                if(s.compareTo(words[m]) < 0) r = m - 1;
                else l = m + 1;
            }
            return -1;
        }

    public static void main(String[] args) {
        System.out.println(new 面试题1005稀疏数组搜索0421().findString1(new String[]{"at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""},"ta"));
        System.out.println(new 面试题1005稀疏数组搜索0421().findString2(new String[]{"at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""},"ball"));
       }

}
